/*
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

链接：https://leetcode.cn/problems/3sum
 */

package LC0015;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

// 太乱了，不要看
// 双指针
public class Solution3 {
    public static void main(String[] args) {
        int[] nums = {-1,-1,-3,2,0,4};

        Solution3 solution = new Solution3();
        System.out.println(solution.threeSum(nums));
    }

    public List<List<Integer>> threeSum(int[] num) {
        // 排序，方便识别重复的数组
        Arrays.sort(num);
        // TODO .sort() ???

        List<List<Integer>> list = new LinkedList<>();
        // TODO 为什么是linkedList???

        // num[i]是第一个数字，从剩下的数字里再找两个数字
        // 将问题转化为两数之和
        for (int i = 0; i < num.length-2; i++) {

            // 为了保证不加入重复的 list,因为是有序的，所以如果和前一个元素相同，只需要继续后移就可以
            if (i == 0 || (i > 0 && num[i] != num[i-1])) {
                // TODO 为什么 num[i] != num[i-1])
                    // 从num[i]能够找到的所有解，肯定已经包含在num[i-1]的解里面了
                // TODO 为什么判断i == 0？？
                    // 否则 num[i-1]就越界了

                //两个指针,并且头指针从i + 1开始，防止加入重复的元素
                int left = i+1, right = num.length-1;
                int sum = 0 - num[i];

                while (left < right) {

                    // 如果是三数之和
                    if (num[left] + num[right] == sum) {
                        list.add(Arrays.asList(num[i], num[left], num[right]));
                        // TODO asList() ???

                        //元素相同要后移，防止加入重复的 list
                        while (left < right && num[left] == num[left+1]) left++;
                        while (left < right && num[right] == num[right-1]) right--;

                        //
                        left++; right--;
                    } else if (num[left] + num[right] < sum) {
                        left++;
                    } else{
                        right--;
                    }
                }
            }
        }
        return list;
    }
}
